我们谈到了，如何能够做出一些非常有意思且简洁的计算证明，比如通过利用多项式复合和除法技术，证明你算出了第一百万个斐波那契数。但是，它依托于一个非常重要的元素：给定一个集合，里面有很多的点，你必须能够证明集合里的大部分点都在同一个低次多项式上（译者注：本文所译的多项式度数或次数，皆对应 degree 一词）。这个叫做“低次测试”的问题，可能是协议中最为复杂的部分。

首先，再次回顾一下我们的问题。假设有一些点，你声称它们都在同一个多项式上，并且该多项式的度少于 D（也就是说，如果度小于 2，意味着这些点在同一直线。如果度小于 3，意味着它们在同一直线或抛物线，等等）。而你想创建一个简洁的概率证明，证明的确如此。

如果你想要验证，这些点 全部 都在同一个度小于 D 的多项式上，那么实际上你将不得不对每一个点进行检查，因为哪怕是仅仅漏掉一个点，也可能会出现差错：漏掉的这个点刚好不在这个多项式上，而其他点恰好都在上面。不过，你可以做的是，在所有的这些点中，概率性地检测至少有部分（比如 90%）点都在同一个多项式上。

左上：可能足够接近于某一多项式；右上：不够接近某一多项式；左下：同时接近于两个多项式，但是又不足以接近任意一个；右下：显然不够接近任一多项式

如果你能够检查多项式上的每一个点，那么问题非常简单。但是，如果你只能够检查几个点呢？——也就是说，你可以要求检查任意几个点，作为协议的一部分，证明者也有义务给你这些点，但是查询次数总数是有所限制的？那么问题来了，你需要检查多少个点，才能在一定程度上进行确认？

显然，D 个点是不够的。因为 D 个点恰好可以唯一定义一个度小于 D 的多项式，所以你得到的 任意 的点集合，都只会与某个度小于 D 的多项式相关。从上图可以看出，D+1 或更多的点，肯定 可以给我们带来更多信息。

给定一些值，通过 D+1 次查询，检测这些值是否在同一个度小于 D 的多项式上，其算法其实并不十分复杂。首先，从 D 个点中随机挑选一个子集，并用像拉格朗日插值法（在 这里 搜索 “Lagrange interpolation” 获得更多介绍）来还原这个唯一的度小于 D 的多项式，并且该多项式能够通过这些所有的点。然后，随机再采样一个点，检测该点是否在同一个多项式上。

第一步：选 D 个点；第二步：还原度小于 D 的多项式；第三步：再检查一个点

注意，这仅仅是一个临近测试（proximity test），因为无可避免地会出现这样一种情况，即虽然大部分点都在同一个低次多项式上，但却有另外一些点不在该多项式上，而第 D+1 个采样点恰好完全地错过了这些点。不过，我们可以对结果进行派生，如果在同一个度小于 D 的多项式上的点低于 90%，那么测试将很大可能失败。具体来说，如果你进行 D+k 次查询，有至少 p% 的点不在同一个多项式上，而其他点却在上面，那么通过测试的概率仅有 (1-p) ^k。

但是，如果像上一篇文章的例子那样， D 非常大，而你想要在少于 D 次查询的情况下，验证一个多项式的度，那该怎么办呢？当然，这不太可能直接“对症下药”， 因为上面已作出了简单的论证（即，任意 k (x ^ y) % p x - y —> (x - y) % p x / y —> (x * y ^ (p-2)) % p 上面的例子都是自洽的。比如，如果 p = 7, 那么：

5 + 3 = 1 (as 8 % 7 = 1)

1 – 3 = 5 (as -2 % 7 = 5)

2 * 5 = 3

3 / 5 = 2 (as (3 * 55) % 7 = 9375 % 7 = 2)

对于像分配律这样更复杂的内容同样成立： (2 + 4)3 和 2 * 3 + 4 * 3 都等于 4。在这种新的数学中，甚至像 (a2-b2)=(a-b)(a+b) 也仍然是成立的。除法是其中最困难的部分：我们无法使用常规除法，因为我们想要结果始终是整数，但是常规除法常常会得到非整数的结果（比如 3/5）。在上面的除法公式中，p-2 次幂是一个使用 费马小定理 直面该问题的结果，它表示对于任意非零的 x < p，都有 x^(p-1)%p = 1.这表明 x^(p-2) 给出一个数，如果再乘以一个 x，得到 1，所以我们可以说 x^(p-2)（是一个整数）等于 1/x。对模块化除法操作符求值，一个有点更为复杂，但是更快的方式是 扩展欧几里得算法，其 Python 实现在 这里。

由于数字“环绕”，模块化数学有时又叫“时钟数学”

通过模块化数学，我们已经创立了一个全新的数学系统，因为它与传统数学在各个方面都是自洽的，所以我们在模块化数学里面讨论各种同样的结构，包括我们以“常规数学”论之的多项式。密码学家喜欢用模块化数学（或者，更通俗一点，“有限域”），因为一个数字的大小有界，它可以作为任意一个模块化数学的计算结果——无论你做什么，值都不会“跳出” {0, 1, 2 … p-1}的范围。

费马小定理还有另一个有趣的结论。如果 p-1 是某个数 k 的倍数，那么函数 x -> x^k 有一个小的“像（image）”——也就是，这个函数只能够给出 (p-1)/k + 1 个可能的结果。比如， x -> x^2 在 p=17 时，只有 9 个可能的结果。

指数越高，效果越明显：比如，x -> x^8 在 p = 17 时，只有 3 个可能的结果。当然， x -> x^16 在 p=17 是只有 2 个可能的结果。如果是 0，返回 0，其他任何都返回 1.

让我们来继续讨论一个稍微复杂点的协议，它的目标在于，将证明者的复杂度从 10^18 降至 10^15，继而降至 10^9。首先，我们并不是针对常规数字进行操作，而是使用模块化数学检查多项式的近似程度。正如在上篇文章所述，在 STARKs 中，我们无论如何都要防止数字增长至 200,000 位。但是在这里，我们将要利用确定的模幂（modular exponentiation）的“小像（small image）”属性，并将其视作为一个副作用，来使得我们的协议更有效率。

具体来说，我们将选用 p = 1,000,005,001。之所以选择这个系数（modulus），是因为：

它比 10 亿大，因为我们需要它至少是 10 亿，这样才能检测 10 亿个点。

它是质数

p-1 是 1000 的偶数倍。

幂 x^1000 的像大小为 1,000,006 ——也就是说，这个幂只有 1,000,006 个可能的结果。

这意味着“对角线”（x, x^1000） 现在变成了一个被包着（with a wraparound）的对角线；因为 x^1000 只可以取 1,000,006 个可能值，所以我们仅需要 1,000,006 行。故而，g(x, x^1000) 的所有取值现在只有 ~10^15 个元素。

这表明，我们可以更进一步地：让证明者仅提交在一个单列上 g 的值。关键技巧在于，原始数据本身已经包含了 1000 个点，而这些点在给定的任意行上，所以我们可以简单采样这些点，推导出它们所在的度小于 1000 的多项式，然后检查列上相关的点在同一个多项式上。再接着检查列本身是一个小于 1000 的多项式。

虽然验证者复杂度仍然是亚线性的，但是证明者复杂度已经降到了 10^9，并与查询次数成线性关系（尽管在实践中由于多项式求值的开销，仍是超线性的）。

虽然证明者复杂度现在已经无法再低了，但是我们仍然可以进一步地降低验证者复杂度，即从二次降至对数。我们的方法是让算法递归。从上面谈到的协议开始，但是并非试图将一个多项式嵌入到一个 x 和 y 度相等的二维多项式中，我们将多项式嵌入到一个二维多项式中，该二维多项式的度 x 下界是一个小的常量值。简单来说，我们甚至可以说就是 2 。也就是说，我们表示 f(x) = g(x, x^2)，所以行检验仅需每个采样行的 3 个点（2 个来自对角线，还有 1 个来自列）。

如果原始多项式的度小于 n，那么行的度小于 2（也就是说，这些行是直线），列的度小于 n/2。因此，我们现在得到的是一个线性时间过程，它将证明一个度小于 n 的近似多项式问题转变为证明度小于 n/2 的问题。进一步地，需要提交的点数，和证明者的计算复杂度，每次会减少 1/2（Eli BenSasson 喜欢将 FRI 的这一点与fast fourier transforms相比较，与 FFT 不同的关键在于，每一步递归都只进入一个新的子问题，而不是将问题一分为二 ）。因此，我们可以简单地继续使用在上一轮协议所创建的列上的协议，直到列变得足够小，小到我们可以简单地直接检查。整体复杂度大概是 n + n/2 + n/4 + … ~= 2n.

实际上，协议将需要被重复多次，因为仍有极大的可能，攻击者会在协议的某一轮作弊。但是，只要证明不是太大，验证复杂度在量级上仍然是对数级，尽管它会上升到 log^2(n) ，如果你把 Merkle 证明的大小也算进去的话。

“真正”的 FRI 协议也有一些其他的修改。比如，它使用一个二分的 Galois 域（另一种奇怪的有限域。本质上，与我在 这里 讨论的第 12 度扩展域是同样的东西，不过素数模是 2 ）。行所使用的指数通常是 4 而不是 2。这些修改提升了效率，并使系统更加友好，在上面更易构建 STARKs。但是，对于理解算法的工作原理，这些修改并非十分必要。如果你真的想要理解算法的话，利用这里所述的基于模块化数学的 FRI，虽然简单了一点，但是应付 STARKs 绝对是够了。

我必须要提醒 计算可靠性（calculating soundness） ——也就是，无论概率有多低，对于给定次数的检查，一个经过优化后的假证明，仍可能会通过测试。——这依旧是这个领域中的“危险”地带。可以简单测试一下，取 1,000,000 + k 个点，有一个简单的下界：如果一个给定的数据集有这样一个属性，对于任意多项式，数据集中至少有 p% 的点没有在多项式上，那么在该数据集通过测试的概率将至多是(1-p)^k。但是，即使下界很低——比如，不可能同时有超过 50% 的点接近两个低次多项式，并且你首先选择的点会是上面最多的点的概率相当低。对于一个成熟的 FRI 来说，仍会涉及各种特定类型攻击的复杂度。

这里 是 Ben-Sasson 等人最近的一篇文章，里面在完整的 STARK fang’an背景下，介绍了 FRI 的可靠性属性。总的来说，“好消息”是，为了在 STARK 上通过 D(x) * Z(x) = C(P(x)) 检查，一个无效方案的 D(x) 将需要是某种意义上的“最坏情况” – 他们需要最大化地远离任意有效的多项式。这表明，我们不需要检查那么近的距离。虽然有已证明的下界，但是这些界限表明一个真正的 STARK 在大小上需要 ~1-3 MB；一个属于推测尚未被证明的更严格界限，减少所需检测次数的 1/4。

​第三部分，将讨论构建 STARKs 的最后一个主要的挑战：如何构建约束检查多项式（constraint checking polynomial），才能够证明任意的计算语句，而不仅仅是几个斐波那契数。

原文链接: https://vitalik.ca/general/2017/11/22/starks_part_2.html 作者: Vitalik Buterin 翻译&校对: & Elisa liuchengxu的简书: https://www.jianshu.com/u/daf68451f175